package com.faiz.algorithm;

import java.util.Comparator;
import java.util.Optional;
import java.util.PriorityQueue;
import java.util.Queue;

public class MergeKLists {

    public ListNode mergeKLists(ListNode[] lists) {
        // 暴力法：直接进行排序
        int l = lists.length;
        ListNode tmp = new ListNode();
        Queue<ListNode> minHeap = new PriorityQueue<>((x, y) -> x.val - y.val);
        // 将数据载入到minHeap中
        for (ListNode list : lists) Optional.of(list).ifPresent(minHeap::offer);

        ListNode buildList = tmp;
        while (!minHeap.isEmpty()) {
            ListNode curMinNode = minHeap.poll();
            buildList.next = new ListNode(curMinNode.val);
            buildList = buildList.next;
            // 再次插入并调整队列
           Optional.of(curMinNode.next).ifPresent(minHeap::offer);
        }
        return tmp.next;
    }

    public static void main(String[] args) {
        ListNode head1 = new ListNode(1);
        head1.next = new ListNode(4);
        head1.next.next = new ListNode(5);

        ListNode head2 = new ListNode(1);
        head2.next = new ListNode(3);
        head2.next.next = new ListNode(4);

        ListNode head3 = new ListNode(2);
        head3.next = new ListNode(6);

        MergeKLists mergeKLists = new MergeKLists();
        ListNode mergedLists = mergeKLists.mergeKLists(new ListNode[]{new ListNode()});

        while (mergedLists != null) {
            System.out.println(mergedLists.val);
            mergedLists = mergedLists.next;
        }
    }
}
